package mySort;
//计数排序
public class CountSort {

    public void countSort(int[] arr) {
        int maxVal = arr[0]; //记录最大值
        int minVal = arr[0]; //记录最小值
        for (int x : arr) {
            if (x > maxVal) {
                maxVal = x;
            }
            if (x < minVal) {
                minVal = x;
            }
        }

        //处理count数组
        int[] count = new int[maxVal - minVal + 1];//计数数组容量
        for (int i = 0; i < arr.length; i++) {
            count[arr[i] - minVal]++;
        }

        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] != 0) {
                arr[index++] = i + minVal;
                count[i]--;
            }
        }
    }
}
